Abstract
The graph isomorphism problem is about deciding whether two graphs are actually the same even if they look different in their graphical or adjacency matrix representation. The problem has important applications, especially in the field of computer science, chemistry and bio-informatics. Moreover, the problem of graph isomorphism has remarkable properties in terms of its complexity, it is not known to be in class P, and also not known to be class NP-complete. These properties make the problem a perfect candidate for the development of a new efficient quantum algorithm. In this direction, we have put some efforts into investigating this question. This paper gives an overview and importance of graph isomorphism problem, discusses the complexity properties and the essentials for quantum computations such as quantum parallelism and superposition, quantum Fourier Transforms, Fourier sampling. An insight into two important approaches for the quantum computations; the Hidden subgroup approach and hidden shift approach have been discussed. However, more emphasis has been on graph isomorphism and its relation to Hidden subgroup problems. In all, we have given a quantum framework for graph isomorphism problem.
Keywords:
Graph isomorphism, quantum computation, Hidden subgroup problem
1.0 Introduction
The graph isomorphism problem is the problem of determining whether two graphs are actually identical even though they “look” differently when they are given in the graphical notation or in the adjacency matrix representation. In other words, we want to know if the vertices of one of the graph can be rearranged such that the second one is obtained. Mathematically, such a “rearrangement” corresponds to a permutation of the set of vertices of one of the graphs. Hence, the naive brute-force method is to check all of such permutations. If our graphs have n vertices each, we have to check n! of such rearrangements. This very quickly becomes infeasible when n grows. In order to attack the problem, we have to use more clever strategies. Even though the problem has been thoroughly investigated for more than few decades now, there is no efficient algorithm known, i.e. it is unknown how to solve the problem with running time that is bounded by some polynomial function in the number of vertices of the graphs. In other words, it is not known if the problem is contained in P.
2.0 Complexity properties of the graph isomorphism problem
A fundamental area of computer science is complexity theory, which investigates the resources (such as time or memory) required to perform computational tasks. The most prominent of these classes are P and NP. The class P consists of the decision problems that can quickly be solved on a Turing machine. More precisely, one demands that the number of steps of the Turing machine required solving the problem to be a polynomial in the size of the input problem. One says that the problem has an efficient solution. There are good reasons for regarding the problems in P to be the problems that are solvable in practice, i.e. that are feasible in reasonable time. The class NP encompasses P and consists of the decision problems that can be solved with polynomial steps by a non- deterministic Turing machine. Another important notion in complexity theory is the completeness of a problem. A complete problem is, in a sense, the hardest problem in a complexity class. Hence, the NP-complete problems are the hardest problems in NP. It is believed that there is no NP-complete problem that has an efficient solution. However, this has not been proved or disproved yet. More precisely, this is the famous question whether P = NP or P ≠ NP, which is still unresolved! In fact, it is one of the most important open questions in computer science. As was already stated, most researchers believe that P ≠ NP [1][2].
Figure 1. Placement of GI among the complexity classes
The graph isomorphism problem is in NP. But so far, all attempts to show that the problem is in NPC, the class of NP-complete problems, have failed. It is known that the set NP - (P È NPC) of “intermediate” problems is not empty if P ≠ NP. One assumes that GI is contained in this set, as indicated in figure 1. The fact that the graph isomorphism problem is probably neither in P nor in NPC and the wide range of applications make it a perfect candidate problem for the search for a new efficient quantum algorithm. Consequently, current quantum algorithm research puts a lot of effort into working on this issue.
3.0 Practical applications of the graph isomorphism problem
The graph isomorphism problem is encountered frequently when structures are investigated using graph representations. Important applications are known in fields like chemistry, bio-chemistry, image processing and artificial intelligence [03]. In this context, the lack of efficient procedures, however, is not that a big problem as one might think. First of all, there are some classes of graphs for which efficient solutions are known. Some of the problems occurring in practice lead to graphs of such classes. Secondly, there are heuristic algorithms that, for practical purposes, deliver results that are good enough.
4.0 Formal definitions related to graph isomorphism
We can assume that for a graph with n vertices, the set of vertices is given by the set V = {1, . . ., n}. Permutations of the vertices are then given by permutations in the symmetric group Sn. Let π Є Sn be a permutation and Γ= (V, E) a graph on n vertices. We write πΓ for the graph that is obtained by permuting the vertices of Γ with π, as π Γ : = (V, πE).
Definition 4.1 Two (directed or undirected) graphs Γ1 = (V, E1), Γ2 = (V, E2) are called isomorphic if there exists a permutation τ such that π Γ1 = Γ 2. In this case, one writes Γ1 approx. equal to Γ2 and τ is called a graph isomorphism between Γ1 and Γ2. The set of isomorphism between a graph Γ1 and a graph Γ2 is denoted by Iso(Γ1, Γ2).
Definition 4.2 The graph isomorphism problem (GI) is defined as follows: Given two graphs Γ1, Γ2, decide if they are isomorphic.
Example: The graphs shown in figure 2 are isomorphic via the permutation Γ.
Figure 2. A pair of isomorphic graphs
Definition 4.3 An automorphism of a graph Γ is an isomorphism on Γ itself, i.e. a permutation of the set of vertices that preserves the graph structure. For a graph Γ, we denote the set of automorphisms by Aut(Γ).
Clearly, each graph has the trivial permutation as an automorphism. Furthermore, it is obvious that Aut(Γ) is a subgroup of the symmetric group: Aut(Γ) ≤ Sn. It is called the automorphism group of the graph.
Definition 4.4 A graph is called rigid if the trivial permutation is its only automorphism, i.e. if its automorphism group is the trivial group.
5.0 Essentials for quantum computation
In the context of solving any problem on quantum computers, we generally require quantum parallelism, entanglement and superposition as the important operations on qubits. In the section below, we will see the importance of these.
5.1 Quantum parallelism and superposition
Let f : {0, 1}p ® {0, 1}q be a function. We know that there is a unitary transformation Uf : |x> Ä |y> ® |x> Ä |y> Å f(x) > which enables a quantum circuit to calculate values of f. The Hadamard transformation H can be used to create an equally-weighted superposition of all states of the computational basis. A combination of these two operations creates the effect of quantum parallelism. This is illustrated in the figure 3. The quantum circuit that transforms the p + q qubit-state as follows:
Figure 3. A quantum circuit that creates the effect of quantum parallelism
=
(1)
Using only p Hadamard transformations and the Uf transformation, we have created a superposition of all of the 2p function values! Does this mean that we have actually computed all of these values now? Unfortunately, this is not the case: In order to “read out” a value f(i) from the state, we have to perform a measurement. However, because of the probabilistic nature of quantum measurements, we cannot choose which value measurements returns; all of the possible results are equally likely. Furthermore, the state collapses to a basis state after the measurement, destroying all of the computed values. Thus, the power of quantum computation does not do well when we want to compute many values of a function f : {0, 1}p ® {0, 1}q. Instead, fast quantum algorithms exploit the effect of quantum parallelism in a more subtle way. Quantum parallelism is only the first step on the way to the creation of superposition.
5.2 Entanglement
A composite system of two component systems A and B is said to be in a product state if the state |ψ> of the system can be written as a tensor product |ψ> = |ψA> Ä |ψB> , where |ψA> and |ψB> are state vectors of the system A, and system B respectively. If the state of the system cannot be written as such a tensor product, the state of the system is said to be entangled. Entanglement plays a very important role in quantum computation and the theory of Quantum Information. However, entanglement is a phenomenon that is not fully understood by scientists yet. How does a pair of quantum systems happen to become entangled? The answer is that entanglement can be created by applying a unitary transformation U on the composite system. If U cannot be written as a tensor product of two Unitarians on the component systems, the system will end up entangled.
5.3 Quantum Fourier Transform
The Fourier transform plays an important role in quantum computation. Computer scientists are familiar with the Fourier transformations of functions f : Zn ® C from numerous applications, such as fast multiplication of polynomials or Fourier descriptors in image compression and calculation of all the irreducible representations of a group element. Quantum algorithms and the problems they solve are usually formulated quite in abstract sense, in the language of groups. In such a formulation, the quantum algorithm does not operate on the complete Hilbert space of a qubit register, but on a subspace that, in some sense, encodes the group elements and the entries in the representation matrices. First of all, we can choose an arbitrary injective mapping from G to the basis states of the computational basis; the state representing g Î G is then written as |g>. In order to define the quantum Fourier transforms, we also need to encode the representations in quantum states. For this, we choose an injective mapping from the set Ĝ of the irreducible representations of G to the computational basis states. Each position (i, j), 1 £ i, j £ dρ in a representation matrix for ρ Î Ĝ with respect to some basis then corresponds to a state |ρ> Ä |i > Ä |j > in a qubit register of the appropriate size. As usual, we also write |ρ, i, j > for this state. The three partial registers will be called representation register, row index register and column index register.
Definition 5.1 The quantum Fourier transform F is defined as the operator that maps a basis state |g> to the corresponding superposition of all irreducible representations:
(2)
5.4 Fourier sampling
This is a very general formulation of a process that aims at solving the hidden subgroup problem. In fact, it is a generalization of the Shor’s factoring algorithm. Fourier sampling consists of a “quantum part” and a “classical postprocessing part”. For the quantum part, a quantum procedure is performed repeatedly, producing (classical) results x1. . . xN. The subsequent classical postprocessing then tries to construct the hidden subgroup H from this information. Fourier sampling can be weak Fourier sampling or strong type based on measurement [04].
5.5 Coset-state algorithms
The basic idea of coset-state algorithms is as follows: We create a quantum state that contains the function values f(g) for all gÎG in superposition, using the effect of quantum parallelism. Because f is constant and distinct on the cosets, we obtain a “superposition over a coset” of H, which contains information about the subgroup H. The Fourier transforms and a subsequent measurement then aims at extracting this information. These techniques of Fourier sampling and coset-state algorithms are of great interest because they are important both for the hidden subgroup approach to the graph isomorphism problem and for the hidden shift approach
6.0 Quantum approach for the graph isomorphism problem
A major breakthrough in quantum computation was the discovery of efficient quantum algorithms for the problems of factoring numbers and finding discrete logarithms by Shor [05]. Furthermore, before Shor’s discovery, some other efficient quantum algorithms were known. The investigation of the common structure of these problems and algorithms soon led to two important approaches for the quantum computations: the hidden subgroup problem and hidden shift problems.
6.1 The hidden subgroup approach
Definition 6.1 Let G be a finite group, X a finite set and f : G ® X a function which is promised to have the following property: G contains an (unknown) subgroup H such that f is constant and distinct on the left cosets of H, i.e. f(a) = f(b) Û aH = bH (Û b-1a Î H) . The hidden subgroup problem (HSP) consists in finding a generating set of the hidden subgroup H. In such a situation, we also say that f hides the subgroup H.
The problems solved by Shor’s algorithms are natural instances of this problem. And almost all quantum algorithms that achieve an exponential speedup are obtained by solving some instances of the hidden subgroup problem. The algorithms that allow such a speedup are instances of a general algorithmic principle, Fourier sampling, or more generally, of coset-state algorithms. The basic strategy is as follows: Repeatedly applying a quantum circuit, we obtain (classical) results x1. . . xN which contain information about the hidden subgroup. A classical post processing step then tries to construct generators for the hidden subgroup (with high probability). We consider the procedure as efficient if the total number of elementary quantum gates and classical post processing steps is polynomial in log |G|. The reason for requiring an efficient procedure to have a running time that is polynomial in the logarithm of the group order is the following: For instances of the hidden subgroup, this definition of efficiency usually corresponds to the definition of efficiency in terms of having running time that is polynomial in the size of the problem.
It has been known that the graph isomorphism problem can be reduced to a hidden subgroup problem over the symmetric group S2n. As the hidden subgroup problem is the quantum algorithmic approach that is best understood, it is natural to investigate if this approach might allow the construction of efficient quantum isomorphism tests. Although there are some non-abelian groups for which the hidden subgroup problem can be solved efficiently, this is not known for the symmetric group. Of course, using the hidden subgroup approach, we need an efficient implementation of the quantum Fourier transforms. However, for Sn, there is an efficient implementation known [06]. Currently, researchers are investigating the question if there might be an efficient hidden subgroup algorithm for the graph isomorphism problem or, more generally, for the symmetric group. The recent results indicate that any efficient coset-state algorithm for the graph isomorphism problem has to make entangled measurements on W(n log n) coset state copies. This is considered as discouraging, as it seems to be hard to efficiently implement highly entangled measurements. Let us now see how the graph isomorphism problem can be formulated as a hidden subgroup problem.
6.1.1 GI as a hidden subgroup problem
Let G1 and G2 be two graphs to be tested for isomorphism. From 4.0, we know that we can assume that both of the graphs are connected. How can we see that the graph isomorphism problem is an instance of the hidden subgroup problem? Of course, there are several ways. We will see one of them.
Hidden subgroup £ Sn 
S2
For each l Î N, let Gl be the class of all connected graphs with l vertices. We write, G := G1 È G2 and define the function f : S2n ® G2n, σ ® σ G.
The function f is constant and distinct on the cosets of Aut(G): Let a, b be two coset representatives. Then f(a) = f(b) Û aG = bG Û b -1aG = G Û b -1a Î Aut(G) Û a Aut(G) = b Aut(G).This shows that the graph isomorphism problem can be stated as a hidden subgroup problem over the group S2n; the hidden subgroup is Aut(G).
6.2 The hidden shift approach
Hidden shift problems are another class of problems that are investigated in
quantum computation. The motivation for considering the hidden shift problem is
the fact that the hidden shift problem in any group G can be reduced to a hidden
subgroup problem over the wreath product group G 
S2. In general, a reduction in the other direction is not
known. Especially, this is true for the group Sn, in which the rigid
graph isomorphism problem can be formulated as a hidden shift problem. Hence,
the considering the hidden shift problem for graph isomorphism seems to be quite
a natural approach [07]. GI can be discussed more generally as a general hidden
shift problem or specifically as to rigid graphs.
7.0 Conclusion
In this paper, we have seen how quantum Fourier transform may be used to solve the hidden subgroup problem, a generalization of the phase estimation and order-finding problems, the problems thought to be intractable on a classical computer. One of the most intriguing aspects of this quantum framework for describing quantum algorithms in terms of the hidden subgroup problem is a suggestion that more difficult problems such as graph isomorphism problem belonging to class Not Possible Intermediate (NPI) might be solvable by considering various groups G and functions f. And on the other hand, this gives us an important clue as to what kinds of problems quantum computers might be good at: in retrospect, the hidden subgroup problem might be thought of as a natural candidate for quantum computation.
8.0 References
[01] Nielsen, M. A., and Chuang, I. L. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
[02] Shor, P. Progress in Quantum algorithms, MIT, Cambridge, USA, 2005.
[03] Jorg Buhler, Dr. Pawel Wocjan. Quantum approaches to the graph isomorphism problem, Institute for Quantum Information, California Institute of technology, Pasadena, CA, 2006.
[04] Grigni, M., Schulman, L., Vazirani, M., and Vazirani, U. Quantum mechanical algorithms for the non-abelian hidden subgroup problem, Combinatorica, 24 (1) (2004), 137–154.
[05] Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5) (1997), 1484–1509.
[06] Beals, R. Quantum computation of Fourier transforms over symmetric groups. Proc. 29th annual ACM Symp. Theory of Computation 32, No.4 (1997), 48–53.
[07] Childs, A. M., and Wocjan, P. On the quantum hardness of solving isomorphism problems as non-abelian hidden shift problems(2006).
Acknowledgements
The authors would like to thank all the authors and publishers for giving us enough information on this emerging area of computing. Our thanks are due to our institute, “The National Institute of Engineering, Mysore” for all the encouragement and support.
Technical College - Bourgas,
All rights reserved, © March, 2000